#include <iostream>
#include <map>

using namespace std;

struct RandomListNode {
	int label;
	struct RandomListNode *next, *random;
	RandomListNode(int x) :
		label(x), next(NULL), random(NULL) {
	}
};


RandomListNode* Clone(RandomListNode* pHead)
{
	if (pHead == NULL)
		return NULL;
	RandomListNode *newHead = new RandomListNode(pHead->label);
	RandomListNode *p = pHead->next, *cp = newHead;

	map<RandomListNode*, RandomListNode*> randomMap;
	randomMap[pHead] = newHead;
	while (p != NULL)
	{
		RandomListNode *copy = new RandomListNode(p->label);
		cp->next = copy;
		randomMap[p] = copy;
		cp = cp->next;
		p = p->next;
	}
	p = pHead;
	cp = newHead;
	while (p != NULL)
	{
		cp->random = randomMap[p->random];
		p = p->next;
		cp = cp->next;
	}

	return newHead;
}


